import java.util.Arrays;
import java.util.LinkedList;
import java.util.List;
import java.util.Stack;


public class Leetcode946 {
    public boolean validateStackSequences(int[] pushed, int[] popped) {
        Stack<Integer> stack = new Stack<>();
        int poppedCheckIndex = 0;
        for (int number : pushed) {
            stack.push(number);
            while (!stack.isEmpty() && stack.peek() == popped[poppedCheckIndex]) {
                stack.pop();
                poppedCheckIndex++;
            }
        }

        return popped.length == poppedCheckIndex;
    }

    /**
     * 数组模拟栈
     */
    public boolean validateStackSequences1(int[] pushed, int[] popped) {
        int[] stack = new int[popped.length + 1];
        int stackIndex = 0;
        int poppedCheckIndex = 0;
        for (int number : pushed) {
            stack[stackIndex] = number;
            stackIndex++;
            while (stackIndex != 0 && stack[stackIndex - 1] == popped[poppedCheckIndex]) {
                stackIndex--;
                poppedCheckIndex++;
            }
        }

        return popped.length == poppedCheckIndex;
    }
}

